\documentclass[11pt,a4paper]{article}

\usepackage{url}
\usepackage{graphicx}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{multirow}
\usepackage{listings}
\usepackage{fullpage}
\usepackage{fancyhdr,a4wide}
% \usepackage{makeidx} %Have commented it out to avoid a strange error about ``missing'' index -- Giordano
\usepackage{placeins}
\usepackage[nolineno]{lgrind}
% \usepackage{dropping} %I don't think we need this package for this report (and then I can avoid to find a way to install it :P ) -- Giordano

\lstset{ %
language=VHDL,                % choose the language of the code
basicstyle=\footnotesize,       % the size of the fonts that are used for the code
showstringspaces=false,         % underline spaces within strings
%numbers=left,                   % where to put the line-numbers
%numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
%stepnumber=1,                   % the step between two line-numbers. If it's 1 each line will be numbered
%numbersep=5pt,                  % how far the line-numbers are from the code
%backgroundcolor=\color{white},  % choose the background color. You must add \usepackage{color}
showspaces=false,               % show spaces within strings adding particular underscores
showtabs=false,                 % show tabs within strings adding particular underscores
escapeinside={\%*}{*)}          % if you want to add a comment within your code
}

\newtheorem{lemma}{Lemma}

\begin{document}	

\begin{titlepage}

\thispagestyle{fancy}
\lhead{}
\chead{
\large{\textit{
Informatics and Mathematical Modelling\\
Technical University of Denmark}}}
\rhead{}
\rule{0pt}{50pt}
\vspace{3cm}

\begin{center}

 	\huge{\textbf{02249 : Computationally Hard Problems}}\\
 	\vspace{1cm}
 	\huge{\textbf{Fall 2007}}\\
 	\vspace{1cm}
 	\huge{\textit{Assignment 6-8}}\\
 	\vspace{1cm}	
	
\end{center}

\vspace{4cm}

\begin{flushright}
	\LARGE{Giordano Battilana (s060675)}\\
	\vspace{0.3cm}
	\LARGE{Risto Gligorov (s060825)}\\
	\vspace{0.3cm}
	\LARGE{Rajesh Bachani (s061332)}\\
	\vspace{0.3cm}
\end{flushright}
\cfoot{\today}
\end{titlepage}

%\begin{abstract}
%\centering
%Abstract to be created.
%\end{abstract}

%-----------------------------------------------------------
\newpage 
\tableofcontents

\newpage 
\section{The Problem}
\subsection{Statement}
\paragraph{Input} A sequence $Y = (y_1, y_2,\cdots, y_n)$ natural numbers and a natural number $K$.
\paragraph{Output} YES if there is a set $I = \{\langle[a_1,b_1],c_1\rangle,\langle[a_2,b_2],c_2\rangle,\cdots,\langle[a_n,b_n],c_n\rangle\}$ of at most $K$ pairs of intervals $[a_i, b_i]$, $1 \leq a_i < b_i \leq (n + 1)$, and natural numbers $c_i$, such that for all $i \in \{1, 2, \cdots, n\}$
\begin{displaymath}
	\sum_{\{j|(i+\frac{1}{2})\in [a_j,b_j] \}} c_j = y_i
\end{displaymath}
Otherwise, output NO.

\paragraph{Output for the optimizing version} Find the minimum number of interval-number pairs $\langle[a_i, b_i]\rangle$, $1 \leq a_i < b_i \leq (n + 1)$, $c_i \in$ N such that for all $i \in \{1, 2, \cdots, n\}$
\begin{displaymath}
	\sum_{\{j|(i+\frac{1}{2})\in [a_j,b_j] \}} c_j = y_i
\end{displaymath}

\subsection{Explanation}
Given a sequence of n numbers Y = $(y_1,y_2,\cdots,y_n)$, the problem is basically to find intervals $(a_k, b_k)$ with weights $c_k$, such that every $y_i$ in Y can be represented as the sum of the weights of all the intervals to which $i+\frac{1}{2}$ belongs. Since the maximum value of $i$ is $n$, we have $1 \leq a_k < b_k \leq (n + 1)$.

Let us consider the simple example, which is given in the problem description. Suppose we have Y = $(2,5,3,3,1)$. A simple and trivial solution for this would be the following intervals, in the form $(a_k, b_k, c_k)$:
\begin{verbatim}
1, 2, 2
2, 3, 5
3, 4, 3
4, 5, 3
5, 6, 1
\end{verbatim}
%\newline
\indent \textbf{Check}:\\ 
\indent $y_1$ = $c_1$ = 2, since $1 + \frac{1}{2}$ belongs to the first interval.\\
\indent $y_2$ = $c_2$ = 5, since $2 + \frac{1}{2}$ belongs to the second interval.\\
\newline
\noindent And similarly, $y_3$ = $c_3$, $y_4$ = $c_4$, $y_5$ = $c_5$.\\
\newline
\noindent Though this is a correct solution, more challenging would be to find the solution in which the number of intervals is minimum. The actual problem is finding the minimum number of intervals whose weights cover all the $y_i$'s. The maximum number of intervals is given as $K$ in the problem statement. Then, for the above example, we could have the following solution:
\begin{verbatim}
1, 3, 2
2, 5, 3
5, 6, 1
\end{verbatim}
\indent \textbf{Check}:\\ 
\indent $y_1$ = $c_1$ = 2, since $1 + \frac{1}{2}$ belongs only to the first interval.\\
\indent $y_2$ = $c_1 + c_2$ = 5, since $2 + \frac{1}{2}$ belongs to the first and second interval.\\
\indent $y_3$ = $c_2$ = 3, since $3$ + $\frac{1}{2}$ belongs only to the second interval.\\
\indent $y_4$ = $c_2$ = 3, since $4 + \frac{1}{2}$ belongs only to the second interval.\\
\indent $y_5$ = $c_3$ = 1, since $5 + \frac{1}{2}$ belongs only to the third interval.\\

This problem is specified in the file \verb,test01.WIC, with the value of K as 3. Since we have solved the problem with 3 intervals, the answer to this problem would be $YES$.

\subsection{Visualization}

The problem can be visualized in a very simple way. Consider $n + 1$ imaginary vertical lines marked from 1 to $n + 1$. The number $y_i$ in Y would hold the position at the vertical line marked $i$. That is, only the first $n$ vertical lines are marked, while the $(n + 1)$th line would not be marked with any number.

Then, intervals can be represented by horizontal lines, such that they start from one of the first $n$ vertical lines, and ends at one of the last $n$ vertical lines. This actually ensures the condition that $1 \leq a_i < b_i \leq (n + 1)$.

In order to check the solution, for the number $y_i$, a dashed vertical line is drawn through $i + \frac{1}{2}$. The weights ($c_k$'s) of all the intervals which are crossed by this dashed vertical line are added. This sum would be equal to the value of $y_i$. 

For the example mentioned above, the visualization would be the following. 
\begin{verbatim}
i    1   2   3   4   5   6
       |   |   |   |   |  
       | ._|___|___|_. |     c1 = 3
     ._|___|_. |   |   |     c2 = 2
       |   |   |   | ._|_.   c3 = 1
       |   |   |   |   |  
yi   2   5   3   3   1     
\end{verbatim}

As we can see, the vertical dashed line for $y_2$ crosses two intervals (2,5) and (1,3) with $c_1$ = 3 and $c_2$ = 2. Any solution to the problem can be visualized in this form, such that all the $y_i$'s can be constructed using a minimum set of intervals. 
\newpage
\section{Decoder to read WIC files}

The problem is coded into the program using a WIC file. The file has to be of the following format:\\
\newline
$N$, $K$, $y_1$, $y_2$, $\cdots, y_n$.\\
\newline
$N$ represents the number of values in the sequence Y, $K$ represents the maximum number of intervals allowed in the solution and 
$y_i$ is the $i$th number of the sequence Y.

The decoder checks whether the format of the WIC file is correct, as per the specifications. This includes the following checks:
\begin{itemize}
\item All the numbers are positive integers. 
\item There are exactly $(N + 2)$ values in the file.
\item The value of $K$ is less than $N$, since the maximum number of intervals that any solution could have is $N$, which is the trivial case.
\end{itemize}
Once the format is verified, all the numbers are loaded into the program. The functionality of the decoder is in the method \verb,decodeInputFile(), of the class \verb,IOHandler, in our implementation.

\newpage
\section{Algorithm}
\input{Algorithm}

\newpage
\section{Proof for WeightedInternalCover in NP}
\input{NPmembership}

\newpage
\section{Proof for WeightedInternalCover in NP-complete}
\label{NPcompleteness}
\input{NPcompleteness}

\section{Who did what}
\begin{itemize}
\item \textit{Giordano Battilana} Algorithm design, algorithm implementation.
\item \textit{Rajesh Bachani} Algorithm design, decoder implementation.
\item \textit{Risto Gligorov} Proof for NP membership and in-NP-complete.
\end{itemize}

\end{document}